#include "DynamicArray.h"

// 动态数组：申请堆空间来创建数组的属于动态数组
struct DynamicArray
{
    ElementType *array; // 数组指针 指向堆上的一个数组空间
    int capacity;       // 数组容量
    int size;           // 元素个数
};

DArray *InitDArray()
{
    DArray *a = (DArray *)malloc(sizeof(DArray));
    if (a == NULL)
    {
        printf("InitDArray malloc error!\n");
        exit(-1); // 退出程序
    }
    a->size = 0;
    a->capacity = 10;
    a->array = (ElementType *)malloc(sizeof(ElementType) * a->capacity);
    if (a->array == NULL)
    {
        printf("InitDArray array error!\n");
        exit(-1);
    }
    return a; // 返回结构体指针
}
   
void InsertDArray(DArray *a, ElementType element)
{
    if (a->size == a->capacity)
    {
        a->capacity *= 2; // 可以扩两倍
        a->array = (ElementType *)realloc(a->array, a->capacity * sizeof(ElementType));
        if (a->array == NULL)
        {
            printf("InsertDArray realloc error!\n");
            exit(-1);
        }
    }
    a->array[a->size++] = element;
}

// void PrintDArray(DArray *a)
// {
//     printf("capacity : %d  size : %d\n", a->capacity, a->size);
//     for (int i = 0; i < a->size; i++)
//     {
//         printf("%d ", a->array[i]);
//     }
//     printf("\n");
// }

void PrintDArray(DArray *a, void (*print)(ElementType))
{
    printf("capacity : %d  size : %d\n", a->capacity, a->size);
    for (int i = 0; i < a->size; i++)
    {
        print(a->array[i]);
    }
    printf("\n");
}

ElementType FindByElement(DArray *a, ElementType value, bool (*compare)(ElementType, ElementType))
{
    for (int i = 0; i < a->size; i++)
    {
        if (compare(a->array[i], value))
        {
            return a->array[i];
        }
    }
    return NULL;
}

ElementType RemoveByIndex(DArray *a, int index)
{
    ElementType result = a->array[index];
    for (int i = index; i < a->size - 1; i++)
    {
        a->array[i] = a->array[i + 1];
    }
    a->size--;
    return result;
}

ElementType RemoveDArray(DArray *a, ElementType value, bool (*compare)(ElementType, ElementType))
{
    for (int i = 0; i < a->size; i++)
    {
        if (compare(a->array[i], value))
        {
            return RemoveByIndex(a, i);
        }
    }
    return NULL;
}

void ClearDArray(DArray *a, void (*clear)(ElementType))
{
    if (a != NULL)
    {
        for (int i = 0; i < a->size; i++)
        {
            clear(a->array[i]);
        }
        free(a->array);
        free(a);
    }
}

void MyFastSort(ElementType *a,int start,int end,bool(*compare)(ElementType,ElementType))
{
    if (start >= end)
    {
        return;
    }
    int left = start;
    int right = end;
    ElementType temp = a[start];
    while (left < right)
    {
        // 从右边往左边找比基准值小的    
        while (compare(a[right] , temp) && left < right)
        {
            right--;
        }
        if (left < right)
        {
            a[left++] = a[right]; // 把比基准值小的数放到左边去
        }
        // 从左边往右边找比基准值大的
        while (compare(temp,a[left]) && left < right)
        {
            left++;
        }
        if (left < right)
        {
            a[right--] = a[left]; // 把比基准值大的放右边
        }
    }
    a[left] = temp; 
    MyFastSort(a, start, left - 1,compare);
    MyFastSort(a, right + 1, end,compare);
}

void FastSort(DArray *a,bool(*compare)(ElementType,ElementType))
{
    MyFastSort(a->array,0,a->size-1,compare);
}

ElementType BinarySearch(DArray *a, ElementType value, int (*compare)(ElementType,ElementType))
{
    int left = 0;
    int right = a->size - 1;
    while(left <= right)
    {
        int mid = left + (right - left) / 2;
        if(compare(a->array[mid],value) == 0)
        {
            return a->array[mid];
        }
        else if(compare(a->array[mid],value) > 0)
        {
            right = mid-1;
        }
        else if(compare(a->array[mid],value) < 0)
        {
            left = mid +1;
        }
    }
    return NULL;
}
